#ifndef _TREE_ARRAY_
#define _TREE_ARRAY_

#include<vector>
using namespace std;
#define lowbit(x) ((x)&(-x))

//获取原数组A的前缀和，即A数组的前x个数之和。
int getPrefixSum(int x, vector<int>& c){
    int ret = 0;
    for ( ; x > 0; x -= lowbit(x)){     //因为C中的每个元素都记录了A中的lowbit(i)个元素之和，所以每次加上C[i]之后，下一次要加上的下标就需要减去lowbit(i);
        ret += c[x];
    }
    return ret;
}

//修改原数组中的第x位置上的元素，将其增加val
void update(int x, int val, vector<int>& c, int n){
    for ( ; x <= n; x += lowbit(x)){    //对于C中的任意一个元素，加上自己包含的原数组个数，就能得到直系父节点的下标。包含原数组个数就是lowbit(x)。
        c[x] += val;                    //这样做是因为，每一个原数组A[i]的改动，都会直接影响C[i]的改动，和所有C[i]的直系父节点，即直系父节点的直系父节点。。。。，所以我们循环向上更新。
    }
}

void createTreeArray(){                 //就等于是初始时C中所有元素都是0，原数组也全是0。然后原数组依次每个元素增加自己对数值大小。
    vector<int> A = {1, 2, 3, 4, 5};
    vector<int> C(A.size() + 1, 0);

    for(int i = 1; i <= A.size(); i++) {
        update(i, A[i - 1], C, C.size());
    }
}

int queryIntervalSum(int i, int j, vector<int>& C){     //获取区间和对方法就是用前j的和减去前i-1的和
    return getPrefixSum(j, C) - getPrefixSum(i - 1, C);
}

void changeNum(int index, int val, vector<int>& C, vector<int>& A) {    //将原数组中的第index个数更改为新的值val，我们就需要对应调用update来更新数组C。
    update(index, val - A[index], C, C.size());
}


#endif